[알고리즘] 이진 탐색

이진 탐색(Binary Search)

데이터가 정렬되어 있는 배열에서 검색 범위를 1/2로 줄여나가면서 검색 값을 찾는 알고리즘.

• 기본적인 탐색 방법 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다.

  • X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로 다시 탐색하고,
  • X가 중간 값보다 크면 배열의 우측의 데이터들을 대상으로 다시 탐색한다.

  

• 활용 방법

  일일이 값을 넣어서 확인해야 하는 문제에서, 범위가 매우 큰 경우 사용하면 탐색에 드는 비용을 크게 줄일 수 있다.

  • 시간 복잡도 비교
    • 단순 순회를 통한 탐색 - O(n)
    • 이진 탐색 - O(log(n))

예제 : BOJ 1939 - 중량 제한

문제 링크

경로 탐색 알고리즘과 이진 탐색을 활용하여 해결할 수 있다. 앞서 알고리즘 개념을 설명하면서 들었던 예시가 특정한 조건을 만족하는 지점을 찾는 것이었다면, 이 문제는 특정한 조건을 만족하는 값 중에서 최댓값을 구하는 문제다.

특정 중량의 물품을 목적지까지 운반할 수 있는지 여부를 검증하는 데에는 [[DFS, BFS]]와 같은 경로 탐색 알고리즘을 사용할 수 있다. 정점(섬)의 개수는 최대 10,000개까지 있을 수 있으므로 복잡도가 적은 인접리스트 방식으로 구현한다.(복잡도(O(n+e))

우리가 탐색할 중량의 범위는 그래프 간선(다리)의 가중치(=중량 제한) 중 최솟값부터 최댓값 사이의 범위인데, 중량의 범위가 1 ≤ C ≤ 1,000,000,000이기 때문에 단순 탐색보다는 이진 탐색을 활용해야 한다. 그림으로 표현하면 다음과 같이 수행할 수 있다.